package shuzu;

public class _04最大小方阵 {
    /**
     * /**
     * * 给定一个N×N的矩阵matrix，在这个矩阵中，只有0和1两种值，返回边框全是1的最大正方形的边长长度。
     * 　　例如：
     * {0, 1, 1, 1, 1},
     * {0, 1, 0, 0, 1},
     * {0, 1, 0, 0, 1},
     * {0, 1, 1, 1, 1},
     * {0, 1, 0, 1, 1}
     * 　　其中，边框全是1的最大正方形的大小是4*4，返回4
     * 创建一个辅助矩阵，每个值是一个（x，y）形式，本身为0时，x和y都是0，为1时，x和y默认为1
     * 此端点右边有多少个连续的1，x就加多少，此端点下边有多少个连续的1，y就加多少，最后使用辅助矩阵判断
     */

    static int[][][] rec;

    public static void main(String[] args) {
        int[][] A = {
                {1, 1, 1, 1},
                {1, 0, 0, 1},
                {1, 1, 1, 1},
                {1, 1, 1, 1},
        };
        generateHelpRec(A);
        print(rec, A.length);
        int res = solve(A);
        System.out.println(res);
    }

    private static void generateHelpRec(int[][] a) {
        int N = a.length;
        rec = new int[N][N][2];
        int row = N - 1;
        //初始化最后一行
        for (int j = N - 1; j >= 0; j--) {
            int value = a[row][j];
            if (value == 1) {
                if (j == N - 1) {
                    rec[row][j][0] = 1;//右侧连续1的个数
                } else {
                    //a的元素值为1，rec在这个位置的连续1的个数=右边位置的连续1的个数+1
                    rec[row][j][0] = rec[row][j + 1][0] + 1;
                }
                //最后一行的下方的1的连续数==1
                rec[row][j][1] = 1;
            }
        }
        row--;
        for (int i = row; i >= 0; i--) {
            for (int j = N - 1; j >= 0; j--) {
                int value = a[i][j];
                //利用右边和下边已经生成的数据来退推出现在这个位置上右侧和下方有多少个1
                if (value == 1) {
                    if (j == N - 1) {
                        rec[i][j][0] = 1;//右侧连续1的个数
                    } else {
                        rec[i][j][0] = rec[i][j + 1][0] + 1;
                    }
                }
                rec[i][j][1] = rec[i + 1][j][1] + 1;//向下来纳许1的个数
            }
        }
    }

    private static int solve(int[][] A) {
        int N = A.length;
        int n = N;
        while (n > 0) {
            for (int i = 0; i < N; i++) {
                if (i + n > N) break;
                l3:
                for (int j = 0; j < N; j++) {
                    if (j + n > N) break;
                    if (check(i, j, n))
                        return n;
                }
            }
            n--;
        }
        return n;
    }

    private static boolean check(int i, int j, int n) {
        //左上角那个点往右数的1的数目要≥n
        //左上角那个点往下数的1的数目要≥n
        //右上角那个点往下数的1的数目要≥n
        //左下角那个点往右数的1的数目要≥n
        if (rec[i][j][0] >= n && rec[i][j][1] >= n && rec[i][j + n - 1][1] >= n && rec[i + n - 1][j][0] >= n)
            return true;
        return false;
    }


    private static void print(int[][][] rec, int N) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.print(rec[i][j][0] + "," + rec[i][j][1] + "\t");
            }
            System.out.println();
        }
    }

}
